/**
 * Created by cc
 * Description:
 * User: CZH
 * Date: 2022-09-25
 * Time: 11:42
 */
public class Test {
    //单链表测试
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(3);
        myLinkedList.addLast(5);
        myLinkedList.addLast(7);
        myLinkedList.addLast(11);
        myLinkedList.show();


        MyLinkedList myLinkedList2 = new MyLinkedList();
        myLinkedList2.addLast(2);
        myLinkedList2.addLast(4);
        myLinkedList2.addLast(6);
        myLinkedList2.addLast(8);
        myLinkedList2.show();

        createCute(myLinkedList.head,myLinkedList2.head);
        ListNode ret = getIntersectionNode(myLinkedList.head,myLinkedList2.head);
        System.out.println(ret.val);

//        MyLinkedList ml = new MyLinkedList();
//        MyLinkedList ml2 = new MyLinkedList();
//
//        ml.addLast(1);
//        ml.addLast(26);
//        ml.addLast(22);
//        ml.addLast(45);
//        ml.addLast(22);
//        ml.addLast(23);
//        ml.addLast(1);
//        ml.show();
//
//        ml.createCycle();
//        System.out.println(ml.detectCycle().val);

//        ml.createCycle();
//        System.out.println(ml.hasCycle());

//        System.out.println(ml.chkPalindrome());

//        ml.deleteDuplication();
//        ml.show();

//        ListNode ret = ml.partition(7);
//        ml.show2(ret);

//        ml2.clear();
//        ml2.addLast(2);
//        ml2.addLast(4);
//        ml2.addLast(6);
//        ml2.addLast(8);
//        ml.show();
//        ml2.show();
//        MyLinkedList newList = ml.mergeTwoLists(ml2);
//        newList.show();

//        System.out.println(ml.findLastKey(4).val);

//        System.out.println(ml.findMiddleNode().val);

//        ml.reverseList();
//        ml.show();

//        ml.removeAllKey(1);
//        ml.show();
//

//        myLinkedList.clear();
//        myLinkedList.show();

//        myLinkedList.removeAllKey1(4);
//        myLinkedList.removeAllKey2(1);
//        myLinkedList.show();

//        myLinkedList.remove(4);
//        myLinkedList.show();

//        myLinkedList.show();
//        myLinkedList.addIndex(0,0);
//        myLinkedList.show();
//        myLinkedList.addIndex(myLinkedList.size(),myLinkedList.size());
//        myLinkedList.show();
//        myLinkedList.addIndex(3,999);
//        myLinkedList.show();

//        myLinkedList.addFirst(11);
//        myLinkedList.addFirst(22);
//        myLinkedList.addLast(11);
//        myLinkedList.addLast(22);
//        myLinkedList.show();

//        myLinkedList.show();
//        System.out.println(myLinkedList.size());
//        System.out.println(myLinkedList.contains(4));
    }



    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        //1.找到长链表，让它先走
        int len1 = 0;
        int len2 = 0;
        ListNode p1 = headA;
        ListNode p2 = headB;
        //计算各自长度
        while (p1 != null) {
            len1++;
            p1 = p1.next;
        }
        while (p2 != null) {
            len2++;
            p2 = p2.next;
        }
///////////////////////////////////////////////
        p1 = headA;
        p2 = headB;
        //判断哪个长
        int len = len1 - len2;
        if (len < 0) {
            p1 = headB;
            p2 = headA;
            len = len2 - len1;
        }
        //让长链表先走
        while (len != 0) {
            len--;
            p1 = p1.next;
        }
        //2.一起走
        while (p1 != null && p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
            if (p1 == p2) {
                return p1;
            }
        }
        return null;
    }


    //找链表相交的节点
    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null) return null;
        if (headB == null) return null;
        //判断链表哪条长度长
        int lenA = 0;
        int lenB = 0;
        ListNode p1 = headA;
        ListNode p2 = headB;
        //各自计算链表长度
        while (p1 != null) {
            lenA++;
            p1 = p1.next;
        }
        while (p2 != null) {
            lenB++;
            p2 = p2.next;
        }
        p1 = headA;
        p2 = headB;
        //保证链表长的是p1
        int len = lenA - lenB;
        if (len < 0) {
            p1 = headB;
            p2 = headA;
            len = lenB - lenA;
        }
        //让长链表先走
        while (len != 0) {
            p1 = p1.next;
            len--;
        }
        //两条链表一起走，相等就是相遇点
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        //判断是不是走完链表都没有相遇
        if (p1 == null && p2 == null) {
            return null;
        }
        return p1;
    }

    //创建两条链表相交
    public static void createCute(ListNode headA, ListNode headB) {
        headB.next.next = headA.next.next;
    }
}
